%Notes:
% anytime a \begin{thing} is used, there needs to be a corresponding \end{thing}
% double quotes are done by using two single quotes

%states the different types of class
%article is being used because of the weird numbering system on the other
%classes, so titlepage has to explicitly stated in this class
\documentclass[titlepage]{article}

%this says to use times as a style and to indent the first paragraph because it 
%does not do that by default
\usepackage{times, indentfirst}

%this allows graphics to be added
\usepackage[pdftex]{graphicx}

%this package is to allow the following \restylefloat which is an override
%that allows the user to explicity state formatting with figures (images)
\usepackage{float}
\restylefloat{figure}

%the following three lines are all for the title and the various \huge, etc are different font
%sizes and there is a difference between \Huge and \huge
%\\* is the escape for new line
\title{\Huge CSE325 Lab 4 Interprocess Communication}
\author{\huge Group 4: \\*  \LARGE Matthew Cramer, Jesse Martinez, Marc Mendoza}
\date{\LARGE \today}

%needed to start the document, think of it like main in normal programming
\begin{document}
%creates the title page based on \title, \author, \date
\maketitle

%this labels a section and it will be numbered in the paper, there is a hierarchy to
%the levels of sections, and curly braces are required
\section{Introduction}
%text can be placed anywhere and it will show up when compiled
This lab explores the usage of inter-process communications (IPC) in an operating system.  Since different managers in the OS may require to communicate between each other, this lab will help to show the communication protocols between the managers.  This documentation contains the description of the IPC Manager used for this program as well as implementation descriptions for the program.

To understand the IPC in detail, an activity and state diagram are described to help understand the flow of the program and how messages are passed in the system.  The Queue Manager is also described to understand how sending and retrieving messages between the managers will take place.  

Finally, a testing plan is described to show what sort of tests will be run on the IPC to ensure its functionality.  The IPC implements queues as the managers in the OS and the Testing Interface will call the IPC manager to execute functions.

To compile the IPC Manager program, run the "compile.sh" script and execute "run" to run the program.

\section{Inter-Process Communication Manager}

The inter-process communication manager (IPC) is a communication manager for different parts of the system.  Each manager in the system requires messages to be passed between each other for processes or other types of information.  This program constructs the managers as queues that can enqueue and dequeue data messages between the different queues.  

The IPC operates on the assumtion that there is another manager to communicate with.  For this reason, the IPC can send messages between 2-10 managers that are determined from the Testing Interface.  Each of the managers, represented as queues, allow messages to be received from managers that are currently in use and can store that data in its queue.  This allows for multiple messages to be retrieved from managers that can be used for process communication when implemented in later labs. The IPC manager will also ensure the managers are maintained and report any errors that may arise.  In order to pass data between queues, the Queue Manager will handle enqueuing and dequeuing the data structures between the queues.  Below is a activity diagram that shows the flow in the IPC manager when a command is passed to the IPC from the Testing Interface (Figure 1).  

\begin{figure}[H]
\begin{center}
\includegraphics[scale=.50]{ActivityDiagram.jpg}
\caption{Activity Diagram}
\end{center}
\end{figure}

The IPC functions with a Testing Interface that will pass commands to the IPC Manager in order to send and retrieve data from the queues.  The IPC manager will handle the commands that are meant for the manager, being the Send, Retrieve, HAS\_Message and init\_IPC commands. These functions will be described later. The testing interface will handle displaying the information for the user with the List function.   Since the Testing Interface handles the arguments for the functions, the IPC manager will assume that all information being passed to the IPC is of correct type.  

\begin{figure}[H]
\begin{center}
\includegraphics[scale=.50]{StateDiagram.jpg}
\caption{State Diagram for Message in IPC}
\end{center}
\end{figure}

This state diagram is only for a message in the system.  All error checking is done by the IPC manager and not the message itself.  This state diagram is only for a successful message that is able to be enqueued onto a queue.

There are three states for a message in the IPC manager(Figure 2): Created, Message Wait, Retrieved.  When a message is requested to be sent from one manager to another, the message moves to the Created state where the message is created in the message struct.  From there, the message is enqueued to the specified queue and enters the Message Wait state where the message waits to be dequeued.  Once the messaged gets dequeued from the queue, the message enters the Retrieved state where it is retrieved from the current manager and transfered to another manager that called it.  This is the final state for this message in this state.
  
\subsection{Manager Actions}
The following are the main functions that the IPC manager will contain along with access to existing queue manager functions in the Queue Manager.
\begin{enumerate}
\item {\bf Send:} This function will receive ({\it source destination message}) where the {\it source} and {\it destination} are both queues. The function will then error check to make sure both queues are valid. The message will then be enqueued onto the destination queue.
\item {\bf Retrieve:} This function will receive ({\it destination}) which will be a valid queue. Then the function will dequeue the head from the {\it destination} queue and return the message variable from the dequeued struct.
\item {\bf HAS\_Message:} This function will receive a queue name from the Testing Interface and will then check that queue if it contains any messages. If the queue size is 0 then the function will return false and if the queue size \(>\) 0 then it will return true to indicate that the queue has at least 1 message.
\item {\bf init\_IPC:} This function will initialize the IPC manager with the manager numbers passed to it. It will accept at least 2 queues to a maximum of 10 queues as defined in the lab. 
\end{enumerate}

\subsection{Description of Elements/Queues}
The IPC manager will handle communications between all the queues that are in the system and determine which queues get messages.  These messages are comprised of different elements that help to navigate the system as well as hold data within the queues.  The queues will be implemented as defined with a head, tail and pointers between the elements structured as a linked list.  Each queue will be one of the ten Managers defined for the IPC Manager.  The following is a break down of how the message structures are arranged and what they contain.

\subsubsection{Source}
This element will hold the source manager that is sending a message to another manager.  This will be used for data stored in queues to know who sent this message.

\subsubsection{Destination}
This element will hold the destination for the message to be sent. The IPC manager will use this to determine which queue to send the data to.

\subsubsection{Message}
This field will hold the data that will be sent from the source manager to the destination manager.  For this project, the message will only consist of an integer that will be placed in the message structure in the correct queue.  This integer will represent random data now that the OS might be sending to different processes for future labs.  This data will be returned when the Retrieve command is issued from the Testing Interface.

\subsubsection{Previous Index}
This is a pointer in the linked list implementation of the queue pointing to the previous element in the queue.  This is used to help enqueue and dequeue elements onto the queue and keep track of where elements are in relationship to the head and tail of the queue.  The head of the queue will have a previous index value of -1, indicating that there is nothing else in the queue before it.  The head of the queue will be where elements are dequeued from.

\subsubsection{Next Index}
This is a pointer in the linked list implementation of the queue pointing to the next element in the queue.  This is used to help enqueue and dequeue elements onto the queue and keep track of where elements are in relationship to the head and tail of the queue.  The tail of the queue will have a next index value of -1, indicating that there is nothing after this element in the queue.  The tail of the queue will be where elements are enqueued.  

\subsection{Run Time}
	Since most of the IPC manager is enqueuing and dequeuing elements from the queues, the running time of the program is O(1), or constant time.  The queues are implemented with a free list that will keep track of the free indices on the queues in order to prevent searching for empty slots that would take O(n). Enqueuing on the queues is constant time since it would just place the incoming message at the head of the free list that will be attached to the tail of the queue and vis. Dequeuing from the queues is constant time since we are removing the head of the list and placing that index at the tail of the free list. The only function that will be linear time, or O(n) would be List and init\_IPC when the Testing Interface will have to go through each queue to list the messages or clear the queues.  Since these functions are not done in the IPC manager, the IPC will still remain constant time.

\section{Queue Manager}
	The Queue Manager class will be implemented for the Inter-Process Communication manager to handle messages being transmitted in the IPC.  The changes inside the queue manager will be that the functions enqueue and dequeue will no longer need to take in any information from the PCB elements inplemented in the previous labs. Instead, a new struct will be handled and will contain the information for the messages that were listed above.  The queues will still be implemented as a linked list with a head, tail, freeHead and freeTail pointer for each queue. The Delete function was also taken out since it is not needed in this program.  Other than these few changes, the Queue Manager will do the same thing as it did in the other assignments, including clearing the queues. 


\section {Testing Plan}
	The functionality of the IPC manager will be tested in several different ways, including capacity, functionality and error checking.  Below is a list of tests we plan to implement on the program.

\subsection {How to compile Test Program}
Tests were conducted by sending commands to the IPC Manager from a Testing program.  This testing program tested the capacity and integrity of the queues in the IPC Manager by expecting values back from the manager.  If the return values were what it expected, the test passed.  For the functionality of the Testing Interface, such as handling the user input and arguments for the commands, expected output samples were generated and compared with the actual output from the Testing Interface that are executed in the script file.  This was done by string comparison of the two output files in order to see if the correct output was given for each functionality test. The testing files are located in their own subfolder "TestingInterface/Tests".

To compile the Test program, run the "compileTests.sh" script and finally execute "runTests" to run the testing program.  The program will list the tests run and if they passed or not.  

\subsection {Capacity}
\subsubsection{Empty Queues}
This test will ensure that when the program starts, all the queues in the program will be empty and the List, HAS\_Max and Retrieve functions will return an error since there are no elements in the queues.  

\subsubsection{Max Queues}
This test will ensure that once the program starts up, there are no messages to begin with in the queues and then max out all the queues with messages.  This will ensure that the program can reach full capacity and that no more than the max number of messages for each queue is enqueued onto it.  The messages will be listed in each queue to check and see if all the messages are in the correct order and that each contain the maximum number of messages for each queue.

\subsubsection {Max Queue/Clear Some}
This test will max out the queues and then dequeue messages from the queue by calling Retrieve to remove some messages and ensure that the free list is working properly.  This will be done by listing the max messages in the queue and then listing it again when messages have been dequeued to ensure the messages are still in order.  Messages will then be Sent to the queue again to make sure we can still use the free list to enqueue more messages onto the queue.  

\subsubsection {Max Queue/Clear All}
This test will be to ensure that once we have maxed out the queues and removed all the messages from them, that the free list will still be functioning and we can enqueue messages back onto the queue.

\subsection {Functionality}
\subsubsection {init\_IPC}
This test will ensure that when the program starts up, that this function must be called first to initiate the managers and use the rest of the functions.  It will also test to see once messages have been added to the various managers, that it will clear only those new managers that are requested now.

\subsubsection{init\_IPC arguments}
This test will make sure that when this function is called, it requires 2-10 arguments that are the managers to be used.  The number of arguments must correspond with the queues to be used for these managers.  If the correct parameters are not listed, error checks will be tested to ensure correct use.  The managers specified will be assigned a queue and this will be tested here as well to ensure it assigns properly.  This test will also check the uniqueness of a manager name.  

\subsubsection{List}
This will ensure that when the List function is called, that it will list all the managers currently being used by the program.  If there are no messages in a queue, it should display "Empty" for that queue.  If an argument is given, it will check to see if it is the right type of argument, being the correct name for the queue in use to be listed.  If the argument is not a  corresponding queue, it will report the error.  If it is, it will display the messages in that queue.

\subsubsection{List Display}
This test will make sure that all the correct messages are being displayed when List is called and in the right order.  It will ensure to display the Source, Destination and Message for each specific message stored in that queue.  

\subsubsection{HAS\_Message}
This test will check to see if there is data in the specified queue.  This will be tested by making sure there is data in a specific queue and then calling the function to see if it finds the data in the queue. If there is data in the queue, the first message will be at the head.  This test will be used to see if the size of the queue is 0 indicating there is nothing in the queues. If there is a message in the queue, the test will will ensure that the IPC manager returns TRUE.  If it does not find data in the queue, it should return FALSE.

\subsubsection{HAS\_Message arguements}
This test will check to see if there is a specified argument, being a queue, to find a message in.  It will check to see if there is one argument.  If there is, it will check to see if that queue name is assigned and in range of the queues allocated for the program.  If these tests fail, it will error.

\subsubsection{Send}
This test will make sure that when the Send function is called with the correct arguments, it will check to see if the queue it is sending to has room to enqueue a message.  If it does not, it should report back an error stating that the queue is full and cannot enqueue the message.  If the queue is not full, it should return 0 to indicate that the message was placed onto the queue successfully.  A list function will then be used to indicate that the message was sent to the right manager.

\subsubsection{Send arguments}
This test will ensure that the correct number of arguments are used for the Send function.  It should have 3 integer arguments, namely the source, destination and message.  For this project, the message will be an integer number. If a character is used as the message, it will error. This test will error if the correct number of arguments are not given.  It will also check to see if the source and destination manager are currently being used for this run.  If they are not, it will report an error.

\subsubsection{Retrieve}
This test will make sure that the Retrieve function correctly dequeues a message from the destination specified.  If there are no messages in the destination queue, it should report the error to the testing interface.  If there are messages on the queue, this test will ensure that the message at the head is retrieved and returned to the Testing Interface to be printed.  

\subsubsection{Retrieve arguments}
This test will check to see if the correct number of arguments are being used for this function, namely the destination argument.  This argument will be an integer for the corresponding queue.  If the argument is not in range of the managers being used currently, it will report an error.


\section{Misc. Design Decisions}
\subsection{Max Queue Size}
For the purpose of this assignment, the maximum number of messages allowed on a queue is 10.  Since there will be 10 IPC managers in the system,this max is small for simplicity and testing purposes.   

\subsection{Static Queues}
For this assignment, the requirements are for 2-10 managers communicating with each other.  This was done to apply a static approach to the system for simplicity and allows for quick access to managers when needed.  Since no system calls can be made in the IPC, this seemed like a good way to allocate the memory right away an arrays but be implemented as linked lists. Only the managers that are used in the system will be cleared when it comes time to reinitilize the queue with how ever many managers are requested.  

\subsection{Manager Naming}
When the Testing Interface calls for managers to be initiated, each string that is assigned for a manager will be assigned a corresponding queue in the system (I.E. if 3 managers are specified, then the first 3 queues will be used for those managers).  This is converted in the Testing Interface since we can use the String.h library in C there to work with strings.  The testing interface will keep track of which manager is using which queue in the system.  The manager names must also be unique and this will be checked as well.  To determine if a given manager is being used in the program, a string comparison will take place.  Since we could only do this using the string library, it was done in the Testing Interface.     

\subsection{Data Type}
For this lab, we will be sending integers as the data messages.  This is for simplicity and can be changed for later implementations if certain types of data needs to be send between managers.  The program will check to see if the message being sent is a integer or a string/character.  If it is a character, it will error and go back to the menu.  


\end{document}